Dyskusja:Graf (matematyka)

Literatura uzupełniająca

Sekcja wskazuje pozycje niewykorzystane przy tworzeniu artykułu, które mogą być wykorzystane do jego rozbudowy.

• Optymalizacja dyskretna. Modele i metody kolorowania grafów. red. Marek Kubale. Warszawa: 2002. ISBN 83-204-2747-9. Brak numerów stron w książce

Do weryfikacji

Skąd informacja: Za twórcę pojęcia grafu uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich.? Prosiłabym o podanie źródła? 4^@ 15:33, 12 maja 2006 (CEST)

Zdaje się, że Rnm dodał [1]. Zapytam, bo sam nie kojarzę takiej informacji. --Nux ^>dyskusja< 16:07, 19 maja 2006 (CEST)

Z en Wiki:

1736: Euler solved, or rather proved insoluble, a problem known as the seven bridges of Königsberg, publishing a paper Solutio problematis ad geometriam situs pertinentis which was the earliest application of graph theory or topology.

Superborsuk ^Ω 02:34, 20 maja 2006 (CEST)

Hm... Zgdonie z tym nie stworzył pojęcia grafu, tylko raczej stworzył pierwszą naukową publikację dotyczącą teorii grafów. --Nux ^>dyskusja< 13:37, 20 maja 2006 (CEST)

Czepiasz się - Right i Wross piszą "pierwszym naukowcem zajmującym się teorią grafów był Euler." i tak samo piszą, że grafem jest siatka jak i automat skończony jak i schemat blokowy - z nimi też sie bedziesz kłócił? Rnm 09:13, 26 maja 2006 (CEST)

To nie jest czepianie się. Moje pytanie było precyzyjne i dotyczyło wprowadzenia samego pojęcia grafu, a nie zajmowania się grafami. Badaniem funkcji też zajmowano się zanim powstała precyzyjna definicja. Jeśli nie ma źródeł (ja ich nie znam), to sporny fragment należy przeredagować, by nie było podobnych "kontrowersji". Nux słusznie zauważył, że fragment zacytowany przez Superborsuka tego nie rozstrzyga. 4^@ 20:13, 14 cze 2006 (CEST)

"...zajmującym się teorią grafów...", a nie "...twórcą grafów..." i tu się zgadzamy :). Może tam piszą raczej, iż siatkę można uprościć do grafu? Bo i siatka i automat (skończy, czy nieskończony) są bardziej skomplikowane niż sam graf, które jako taki możnaby zgrubsza reprezentować. Np. siatkę topologiczną terenu można zareprezentować jako graf z wagami, żeby rozwiązać problem najkrótszej drogi. Wystarczy wgryźć się w formalną definicję grafu, żeby zobaczyć gdzie jest różnica. No chyba, że ktoś gdzieś tam widzi np. podział wierzchołków na rodzaje: "wykonaj", "wybierz" itp (występujące w schematach blokowych). Czy występuje tam jakieś zdanie podobne do tego: "do każdego wierchołka przyporządkowane są dwie liczby, które stanowią o jego pozycji"? W en:Graph_(mathematics) przynajmniej od razu wiadomo czym z grubsza jest graf, a tutaj początek jest jak dla mnie bardzo mylący i tego się czepiam. --Nux ^{zostaw notkę} 11:13, 26 maja 2006 (CEST)

PS: A przy okazji - skąd pochodzi pojęcie grafy geometryczne? Może to jakieś diagramy chodzi?

graf to zbiór punktów/kwadratów/łososi połączonych krawędziami/linkami/czarnymi dziurami - to mówi definiicja grafu - dwa 'zbiory i funckja z par pierwszego w drugi. I tak oto zgodnie z tą defincją wymieniane przezemnie rzeczy są "pelnoprawnymi" grafami. To prochę tak jakdybyś się czepiał definicji pojazdu - pojazd to coś jeżdzące, ale nie samochód bo on ma karoserię, 4ry koła i inne rzeczy których nie ma pojazd. Tylko że to o polimorfizm chodzi, niektóre rzeczy są szczególnym rodzajem rzeczy innych, co nie sprawia, że nie są tymi innymi :)

określenie grafy geometryczny pochodzi z zarysu teorii grafów - nie chodzi o diagramy, ale o to czy np. dany graf można "upchać" w danej przestrzeni, albo np. o czy da się go tak ustawić, by wszystkie krawędzie miały tą samą długość w konkretnym przedstawieniu grafu. Wytlusciłem to, bo odnoszę wrażenie, że nie do końca rozumiesz różnicę między pojęciem grafu a jego konkretnymi rysunkami Rnm 12:23, 26 maja 2006 (CEST)

O ile wiem mówi się raczej o geometrycznej teorii grafów, czy mógłbyś podać jakieś źródło, gdzie występuje pojęcie graf geometryczny? Kuszi 19:02, 14 cze 2006 (CEST).

Definicja z którą się częściej spotykam traktuje graf jako dwa zbiory: zbiór wierzchołków i zbiór par wierzchołków. Nie rozumiem wypowiedzi wikipedysty Rnm - można mówić o grafie automatu, nie znaczy to jednak, że oba obiekty są tożsame. Kuszi 18:51, 14 cze 2006 (CEST).

Formalna definicja

Czy aktualna formalna definicja

$\!\gamma$ funkcją ze zbioru krawędzi w dwuelementowy podzbiór zbioru wierzchołków - $\!\gamma :E\to \{v,u\}$ gdzie $v,u\in V$

jest poprawna? Bo ten wzór mówi, że wartościami funkcji są elemty zbioru {u,v}. Wydaje mi się, że powinno być coś takiego:

$\!\gamma$ funkcją ze zbioru krawędzi w zbiór dwuelementowych podzbiorów zbioru wierzchołków - $\!\gamma :E\to \{\{v,u\}:v,u\in V\}$

royas 08:25, 6 sie 2006 (CEST)

Słusznie, jest źle. Tak jak napisałeś jest lepiej. Jeszcze lepiej, bo prościej, byłoby zdefiniować graf jako dwójkę, tak jak np. w książce "Wprowadzenie do teorii grafów" Wilsona. Kuszi 10:10, 12 sie 2006 (CEST).

Graf mieszany

Fragment

Jeżeli graf skierowany zawiera dwie krawędzie skierowane \! (v,u) i \! (u,v), to nazywany jest grafem mieszanym.

nie zgadza się z definicją w graf mieszany. Która jest prawidłowa? royas 08:25, 6 sie 2006 (CEST)

W zasadzie obie można uznać za poprawne. Graf mieszany zawiera krawędzie nieskierowane i skierowane (łuki). Przy czym krawędź nieskierowaną można modelować dwoma łukami łączącymi te same wierzchołki. Pozdrawiam Kuszi 10:21, 7 sie 2006 (CEST).

Można modelować to nie znaczy, że są to te same grafy. Właściwie to jest głębsza różnica między tymi dwoma definicjami. Pierwsza to graf, który zawiera jakieś tam krawiędzie, durga - może zawierać, ale nie musi, bo E lub A może być puste. royas 20:45, 20 sie 2006 (CEST)

Osobne definicje

> Ścieżka w grafie to ciąg wierzchołków połączonych krawędziami.

Mam taką wątpliwość, czy warto pisać artykuł "ścieżka" - skoro tak naprawdę jest to krótko i dobitnie opisane tutaj (w grafie)?

A może tu skasować, napisać osobny artykuł o ścieżce i utworzyć link do niego?

To samo dotyczy: cyklu, grafu planarnego, itd.

Grzegon "McCartney" Olędzki 23:25, 8 kwi 2003 (CEST)~

Rozwinięcie artykułu

Początek uczyniłem, bardziej literackim, żeby czytelnika nie odstraszać nudną listą. Sądzę, że wszystkie zagadnienia dotyczące drzew (wyrażenia, binarne itp) należy pominąć. Mamy oddzielny artykuł o drzewach i tam najlepiej to opisać, a tutaj najlepiej skupić się na zagadnieniach typowych dla grafów. W tym momencie mamy 12 stron A4 i spis treści na cały ekran. Więcej treść raczej rozsadzi tekst od środka, więc należy się zastanowić nad niewielkim rozbiciem. Na początek sądzę, że jednak lepiej byłoby w artykule o grafie skupić się na matematycznej definicji grafu skierowanego - to przypadek najbardziej ogólny. Szczególne przypadki grafu nieskierowanego i mieszanego najlepiej opisać w ich artykułach. Superborsuk ^Ω 02:23, 29 kwi 2006 (CEST)

Zsynchronizowanie macierzy

Jakby ktoś mógł, to dobrze by było "zsynchronizować" macierze incydencji i krawędzi i resztę, tak żeby wszystko przedstawiało ten sam graf. Nux ^{zostaw notkę} 19:33, 4 cze 2006 (CEST)

ależ właśnie przedstawia :) RnM - ^D#&%kutuj

Potrzeba dopracowania

Trzy miesiące temu Nux bez podawania konkretnych zarzutów wrzucił infoboc do dopracowania. Czy waszym zdaniem jeszcze coś trzeba tu dopracować? Superborsuk ^Ω 02:12, 20 sie 2006 (CEST)

Lokalnie dużo dobrej informacji, ale spójrzmy na artykuł całościowo. IMHO wstęp-definicja nie najlepsze: po ogólnym uproszczonym opisie powinna zaraz pójść definicja formalna - tak jak stoi to drugi akapit posługuje się pojęciami niezdefiniowanymi. Mimo że mamy tu linki to w porządnym pisaniu tego się bardzo unika. Z resztą ten akapit raczej niewiele już wnosi, bo wiele załatwiłaby w tym miejscu dobra definicja. Kolejne akapity opisują coś, co raczej powinno się zebrać w osobną sekcję "Zastosowania" i przenieść poza wstęp gdzie chyba jest miejsce na podstawowe definicje i objaśnienia. Jeśli nie będzie obiekcji to spróbuję to podrzeźbić - właściwie chodzi raczej o pewne przetasowanie niż zmianę treści. --Beaumont 19:55, 20 sie 2006 (CEST)

J.w. tzn popieram zdanie Beaumonta. Poza tym art robi się trochę przydługi. Można by ewentualnie przenieść zastosowania do osobnego artu, albo do teorii grafów. Cała sekcja o przechowywaniu w pamięci nie musi wszystkich interesować, mogłaby pójśc do nowego artu, powiedzmy Algorytmy grafowe, zwłaszcza że jest już taka kategoria. Z drugiej strony brakuje choćby wzmianki o uogólnieniach, takich jak hipergrafy. Kuszi 20:53, 20 sie 2006 (CEST).

Jeszcze drobna uwaga. Pojęcie graf geometryczny nie wydaje się dobrze ugruntowane, zwłaszcza w języku polskim. Byłbym wdzięczny za jakąś notkę, gdzie zostało ono użyte. Kuszi 20:53, 20 sie 2006 (CEST).

Dzięki za post. Dla porządku:

• Grafy geometryczne po polsku jakoś nieznane(gugel milczy), ale po angielsku całkiem całkiem. Najwidoczniej to nowy prąd który - jak wszystko teraz - pisze się po angielsku... Tutaj podaną definicję można by doszlifować, ale nie jest taka zła, a na pewno lepsza niż stub w enwiki. Ja bym to włączył do sekcji "Klasy grafów".
• Tak samo uwaga o "Grafach nieskończonych" nie zasługuje na osobną sekcję, to przypisek do definicji, tyle że od niej oddzielony
• no i teraz mamy trzy definicje:najpierw na początku, potem sekcja "Definicja", potem coś-tam i dalej "Definicja formalna". Nux miał rację. Poprawimy ;) pozdr. --Beaumont 22:52, 20 sie 2006 (CEST)
• Aha, przyjrzałem się formalnej definicji i mam poważną wątpliwość co do pętli w przypadku grafu nieskierowanego: tam jest źle bo {v,v}={v} więc zbiór jednoelementowy. W linkowanej książce on-line pętle definiuje się tylko dla grafów skierowanych i tam to ma sens. Trzeba to wszystko poprawić - może zmieniając def. grafu skierowanego jak sugerowałeś, na dwójkę (V,E). No, jest nad czym pracować! jeszcze trochę się przyjrzę i idę robić. pozdr. --Beaumont 23:32, 20 sie 2006 (CEST)

• Zdefiniowanie jako dwóki (V,E) raczej nie poprawi sytuacji z pętlą, bo i tak wtedy E musiałoby być podzbiorem zbioru jedno i dwuelemntowych podzbiorów V; co równie dobrze można włożyć do definicji z trójką. No właśnie chyba lepiej zamiast {V,E,g} dać (V,E,g} lub <V,E,g>. royas 00:21, 21 sie 2006 (CEST)

• To bardzo dobry pomysł. Przeniósłbym jeszcze gęstość grafu z definicji do pojęć podstawowych. royas 00:21, 21 sie 2006 (CEST)

• wyjaśniam więc: proponowałem - tak jak Kuszi - "dwójkę", bo tak prościej a nie dlatego że to rozwiązuje problem pętli. Z grubsza graf to dwójka (V,E) gdzie V to wierzchołki a E to krawędzie czyli rodzina dwuelementowych podzbiorów V, i już. Zapisu (V,E,g} nie rozumiem , sorry, a zapis <V,E,g> czyli trójka uporządkowana nic nie zmienia w porówaniu a aktualną wersją, sorry, nie o to chodziło.

• Błąd, miało być (V,E,g), ale nieważne teraz. Definicja z trójką jest o tyle lepsza, że obejmuje również multigrafy, ale się nie upieram, moża ją przenieść do multigrafu. royas 11:33, 21 sie 2006 (CEST)

• Chodzi o to żeby raczej w ogóle nie definiować pętli dla grafów nieskierowanych. Na obrazku jest ona łatwa do pomyślenia a formalna definicja nie pasuje. Jak chesz mieć pętlę w grafie (pozornie) nieskierowanym to musisz zdefiniować graf skierowany symetryczny i tam to istnieje. A najlepiej w ogóle nie definiować formalnie grafu nieskierowanego, tylko skierowany bo tak ogólniej - i problem znika: V to zbiór wierzchołków a E, krawędzie, to pary uporządkowane. Powtórzę - w takim ujęciu graf nieskierowany jest równoważny zywkłemu grafowi symetrycznemu. Krótko: gdyby ktoś miał porządną książkę matematyczną (do definicji formalnej) to by coś zapodał? - Kuszi, masz tego Wilsona to wal śmiało, jak nie to mocno proponuję to co tu powyżej. Pozdr --Beaumont 10:23, 21 sie 2006 (CEST).

• Faktycznie, można nie definiować, będzie poprostu definicja grafu bez pętli. Trudno określić który graf jest najbardziej podstawowy, więc można wybrać to co najprostrze, czyli nieskierowany, nie multigraf, bez pętli, bez wag. royas 11:33, 21 sie 2006 (CEST)

• To zasadniczo racja, ale zauważ że wszystkie reprezentacje w tym artykule (macierz sąsiedztwa,lista sąsiedztwa i macierz incydencji) faktycznie reprezentują graf *skierowany*, no więc dla spójności artykułu trzeba by ten skierowany zdefiniować. Czyli po tym namyśle mogłyby być dwie definicje skierowanego i nieskierowanego, tyle że już bez pętli --Beaumont 13:02, 21 sie 2006 (CEST)

• Oczywiście. Chodziło mi o prostszą definicję grafu nieskierowanego (czy z pętlą, czy bez). Skierowany jak najbardziej zostawić. Fajnie i dosyć jasno jest to zrobione na enwiki. Fragment przetłumaczyłem na Wikipedysta:Royas/graf royas 13:43, 21 sie 2006 (CEST)

• To jest ok. Zwróć tylko uwagę na pisownię "uporządkowany". Poza tym wydaje mi się że w języku polskim digraf nie istnieje, mówi się po prostu graf skierowany (rzut oka w google pokazuje że digraf to firmy nie grafy, ale może niedokładnie patrzyłem - jak masz jakiś ważny przykład używania to zostaw). No i chyba można by już zmieniać definicję tak jak proponujesz (potem ewent. dalsze porządki). --Beaumont 13:55, 21 sie 2006 (CEST).

• A w czym problem z tą petlą? {v,v} - to zbiór dwuelementowy i jest różny od {v}. --Maciej "Nux" Jaros **zostaw notkę** 05:33, 21 sie 2006 (CEST).

• No nie wiem. Zobacz Inkluzja (matematyka). Równość zbioru to nie "taki sam wygląd" tylko formalnie dwie inkluzje, a wygląda mi - o dziwo! - że zgodnie z formalną definicją mamy {v,v}$\subset${v}. Jeśli zamiast zbioru weźmiemy parę uporządkowaną, problem zniknie bo para (v,v) ma sens. Notabene zdaje się jak reprezentujemy graf w komputerze to z logicznego punktu widzenia zawsze mamy do czynienia z parami uporządkowanymi (albo ciągami) czyli robimy de facto graf skierowany i nie ma problemu. Tu zaś mamy pewien problem formalny - może mało ważny w praktyce - ale to w końcu encyklopedia i jakoś trzeba to zwalczyć. Pozdr. --Beaumont 10:23, 21 sie 2006 (CEST)
• A i B są równe gdy dla każdego x: x należy do A wtedy i tylko wtedy gdy x należy do B. Więc {v,v} = {v} i oba są zbiorami jednoelemtowymi. royas 11:33, 21 sie 2006 (CEST)

• No właśnie, dzięki że tak to prosto ująłeś. No i z tego widać że w naszej definicji formalnej mamy pewien błąd. --Beaumont 13:02, 21 sie 2006 (CEST)

• Coś wam obu się pokręciło - podstawmy sobie pod v banknot stu złotowy. Czy jeśli mam zbiór dwóch takich banknotów, to jest on zawarty w zbiorze składającym się z jednego banknotu ;)? Zamiast formalnych rozważań czasem wystraczy trochę logiki. Matematyka naprawdę stara się odnosić czasem do rzeczywistości ;). Natomiast uporządkowanie takiego zbioru już specjalnie nie ma sensu, chyba że banknoty traktujemy jako rozróżnialne, ale wtedy to jest (v1,v2). --Maciej "Nux" Jaros **zostaw notkę** 16:15, 21 sie 2006 (CEST)

• Hm, mocne wejście. My tu jednak o definicji formalnej mówimy, więc potrzeba dużej ścisłości, logika w znaczeniu "zdrowy rozsądek" może nie wystarczać... Przemyślisz?. --Beaumont 21:53, 21 sie 2006 (CEST)

• PS: Tu przy okazji wniosek, że pętla jednokierunkowa nie ma właściwie sensu.
• czy ktoś mówił o pętli jednokierunkowej? Ja tylko o pętli w grafie skierowanym, a to na pewno istnieje i ma prosty sens: ot para (v,v) w zbiorze krawędzi, jedynka na przekątnej macierzy sąsiedztwa (w grafie nieskierowanym też istnieje ale na pewno trza inaczej definiować - tu jużeśmy się dogadali!), na rysunku też łatwo to zobaczyć, nieprawdaż? --Beaumont 21:53, 21 sie 2006 (CEST)

• Chociaż nie może to nie był dobry przykład z tymi banknotami... Chwilowo zgupiałem i jadę poradzić się fachowca (jak to się odmienia przec płcie?) :). --Maciej "Nux" Jaros **zostaw notkę** 16:25, 21 sie 2006 (CEST)

• Hm, nigdy nie wiesz z kim na wiki rozmawiasz... a może royas jest także niezłym fachowcem ? ;) A tak bardziej serio - daj znać o ewentualnych wynikach. --Beaumont 22:05, 21 sie 2006 (CEST)

• Przez fachowca miałem na myśli matemtyczkę :). Jak zaczęła wchodzić na teorię mnogości, to przyznaję, że zacząłem się trochę gubić ;), ale w każdym razie wyszło na to, że rzeczywiście {v,v} jest formalnie zawarty w {v}. Jak by się chciało kombinować, to można ewentualnie zmienić {v,v} na {{v},{v}} i wtedy będzie się zgadzało, ale chyba nie ma potrzeby, bo pętla może być spokojnie zbiorem jednoelementowym {v}. Uporządkowanie natomiast także w jej opinii nie ma sensu. Przypomniała mi też, że tak naprawdę najlepszą definicją jest ta z funkcją gamma (wspominaną już wyżej), bo w sumie bardzo istotne jest to, że krawędź jest przyporządkowana do wierzchołków. No, ale obecna wersja jest chyba OK. A tak przy okazji, to mój przykład był nie bardzo, bo nie wziąłem pod uwagę, że to sytuacja, w której ten sam banknot (obiekt) stu złotowy mam dwa razy, a nie mam ich dwa :). --Maciej "Nux" Jaros **zostaw notkę** 02:41, 22 sie 2006 (CEST)

• No cóż, a może royas jest również matemtykiem ? A tak serio, to oczywiście rozmowa może być pożyteczna (jak tutaj), ale przy okazji pamiętajmy że opinie fachowców, zwłaszcza anonimowych, nie są weryfikowalne i nie stanowią argumentu; opieramy się na źródłach i gdybym akurat miał jakieś pod ręką nie byłoby tej dyskusji. A tak robimy trochę po amatorsku - ale coś tam przynajmniej wychodzi ;) Pozdr. --Beaumont 09:41, 22 sie 2006 (CEST)

• Bardziej czuję się informatykiem(uni), ale nie mam tego na piśmie ;) jeszcze. Myślę, że za parę dni uda mi się zerknąć do paru fachowych książek. royas 10:26, 22 sie 2006 (CEST)

• no to wiemy jak się odmienia przez płcie fachowiec :) Czyli z pętlą mamy ustalone. Nie jestem przekonany czy {{v},{v}} by coś zmienił bo to to samo co { {v} }. Jeśli chodzi o definicję z gammą, to zostawiłbym ją w wariantach, ale przerobił z zbioru na trójkę - w literaturze stosuje się to wymiennie (zbiór jest mniej precyzyjny), a byłoby analogicznie jak w pierwszej definicji. No i jeszcze kwestia notacji czy krotki zapisujemy w "<>" (jak w krotka czy w "()" (jak np. w grupa (matematyka). Chociaż to pytanie trzebaby zadać na jakimś większym forum, bo fajnie by było żeby kiedyś to ujednolicić w całej wiki (przynajmniej działami).

• trafna uwaga co do {{v},{v}}, zgoda co do reszty (definicja z gamą i notacja); pytanie na forum -ok, tylko gdzie? W źródłach nie ma tu zdaje się jednolitego podejścia i jest to trochę kwestia gustu; jak wybierzemy tak możemy ujednolicić. --Beaumont 12:16, 22 sie 2006 (CEST)

• Chodziło mi o póżniejsze ujednolicane między artykułami. Ale to teraz nie jest istotne royas 13:32, 22 sie 2006 (CEST)

{ {v},{v} } to nie jest to samo co { {v} } - tu oszustwo ;) polega na tym, że te dwa zbiory można uznać za różne obiekty i wtedy pierwszy {v} jest różny od drugiego {v}. Tak przynajmniej to zrozumiałem. No, ale to rozważanie czysto akadamickie, bo nie widziałem nigdzie takiej reprezentacji. --Maciej "Nux" Jaros \\ zostaw notkę // 14:56, 22 sie 2006 (CEST)

Jak spojrzysz do wikipedii Inkluzja (matematyka) albo multizbiór albo na definicję równości zbiorów royasa powyżej, to może jeszcze zmienisz zdanie ;) No chyba że w wyższej teorii logiki są lepsze subtelności (wtedy jednak nazwać je po imieniu i źródle). I zgoda, że nie ma tu o co się spierać bo artykułowi to niepotrzebne. Pozd --Beaumont 16:18, 22 sie 2006 (CEST).

To podstawmy {v}=a wtedy mamy { {v},{v} }={a,a}={a} co zgdnie z założeniem ={ {v} } :) Po prostu nie można {v} traktować jak coś innego od {v}, bo mówimy tu o zbiorach matematycznych, a nie informatycznych. Gdyby {v} mogło być czymś innym od {v} to zbiór potęgowy możnaby napompować w nieskończoność. :) A tak nie jest. No ale faktycznie teraz nie ma to znaczenia dla tego art.

Wstęp

Trochę przerobiłem ten wstęp. Wydaje mi się zbyt ogólnikowy i w sumie większości to trochę takie, przepraszam za wyrażenie, "lanie wody", ale szkoda mi było kasować, bo w sumie ktoś się przy tym napracował. Dlatego ciągle liczyłem na to, że zmieni autor. --Maciej "Nux" Jaros **zostaw notkę** 05:33, 21 sie 2006 (CEST).

Grafy, reprezentacje, izomorfizy

Zacznę od tego, że w tym artykule w sekcji o izomofizmie grafów dosyć dużo jest o ich graficznej reprezentacji, natomiast w izomorfizm grafów nic o tym nie ma. Z pierwszej definicji wynika m. in., że grafy różniące się tylko ich reprezentacją, są izomorficzne. A tak naprawde (zgodnie ze wszystkimi zaprezentowanymi definicjami grafów, są to te same grafy, czy też raczej jest to ten sam graf, więc tak naprawdę to ciężko nawet mówić, że on/one(?) się czymś różnią. Różnią się jego reprezentacje. Więc tu należałoby usunąć wszystkie wzmianki o reprezentacji grafu.

Z drugiej strony są jednak miejsca gdzie przez graf rozumie się konkretną reprezentację graficzną (graf płaski, ściana, konstrukcja grafu dualnet) i dlatego możliwe, że trzeba o tym jakoś napisać. No i jeszcze pojawiło się gdzieś pojęcie izomorficzne przedstawienie.

Do literatury narazie nie mam dostępu. Gdyby ktoś miał i sprawdził pod tym kątem... royas 13:32, 22 sie 2006 (CEST)

Różnica polega tylko na tym, że zmieniane są etykiety wierzchołków, więc są to prawie te same grafy, ale nie są te same (dokładnie nie muszą być te same). Zobacz też w artykule głównym :). --Maciej "Nux" Jaros \\ zostaw notkę // 01:00, 24 sie 2006 (CEST)

Wycofane zmiany notacji

Zmiany zostały cofnięte poniważ ich autor nie przedstawił żadnych źródeł, na których oparł swoje modyfikacje. Uprzednia treść artykułu była efektem pracy wielu osób korzystających przy tym z fachowej literatury. Nowe modyfikacje nie zostały w ten sposób zweryfikowane. Superborsuk ^Ω 23:46, 25 gru 2006 (CET)

Uzasadnienie potrzeby modyfikacji artykułu zgodnie z zasadą weryfikowalności leży po stronie osoby ją proponującej, ale ze względu na nalegania autora postanowiłem wypunktować błędy oraz nieścisłości w wycofanej edycji:

• Oznaczenie pary uporządkowanej <V,E> jest zgodne z definicją, która została zaproponowana przez Kuratowskiego,
• Oznaczenie (V,E) zastosowano w
  • Graf dwudzielny - tu trzeba się zastanowić, ale sądzę że dla trójki uporządkowanej też powinno być podobnie, nad tą definicją trzeba popracować
  • Twierdzenie o kojarzeniu małżeństw
  • Graf skierowany - to mój błąd powstały podczas przeniesienia treści z graf kiedy oznaczenie było jeszcze niepoprawne, poprawiłem

Niektóre modyfikacje stylistyczne wprowadzają błędne informacje:

Graf – to - w uproszczeniu - zbiór wierzchołków połączonych...

Tu nie ma żadnego uproszczenia. Zbiór stanowi podstawowe pojęcie teorii mnogości, a krawędź pojawia się w wielu działach matematyki. Definicja zawsze odnosi się do pewnych aksjomatów. Powinniśmy się trzymać ścisłego języka matematyki, gdzie pojęcie "uproszczenia" w tym sensie nie istnieje.

Nie twierdzę, że ani jedna zmiana nie jest poprawna lub neutralna. Niestety autor wprowadził wiele znaczących zmian i szereg drobnych przez jedną edycję. Nie podważam potrzeby pracy nad artykułem, ale sądzę, że tak zasadnicze zmiany wymagają uzasadnienia oraz podania źródeł. Gdyby te same zmiany wprowadzono z podaniem polskiej literatury źródłowej moja opinia byłaby zupełnie inna, bo wiem że notacja stosowana przez różnych autorów bywa odmienna.

W angielskiej Wikipedii hasło en:Graph (mathematics) stosuje oznaczenie pary z nawiasami. Jednak w polskiej szkole matematycznej w wielu przypadkach używane jest oznaczenie z nawiasami ostrymi. Sądzę, że powinniśmy w polskiej Wikipedii zachowywać lokalny charakter pewnych artykułów mających związek z naszą kulturą. Różnice w oznaczeniach grafów są wyrazem takich odmienności w języku matematyki. Polskie słowa całka czy pochodna też odbiegają swoimi źródłami od terminów stosowanych na całym świecie. Powinniśmy uszanować dorobek polskich matematyków na tym polu, stosując stworzoną przez nich notację.

Superborsuk ^Ω 02:13, 26 gru 2006 (CET)

Niestety, nie mogę się zgodzić się z powyższą argumentacją.

• Jak już napisałem na stronie dyskusji Superborsuka, nie mam nic przeciwko konsekwentnemu stosowaniu notacji <x,y>. Po wycofaniu mojej edycji nadal występuje raz <x,y> raz (x,y).
• Chciałem ponadto zauważyć, że absolutna większość artykułów na Wiki używa notacji (x,y) (mogę zrobić listę jeżeli potrzeba). O ile Polacy nie gęsi i swoje całki mają, to notacja matematyczna jest międzynarodowa. Poza tym, w graf skierowany przed zamianą notacji było używane (x,y) a po zamianie jest używane niekonsekwentnie raz <x,y> raz (x,y). Wszystkie linki z graf (matematyka) prowadzą do artykułów z notacją (x,y) oprócz 5 - graf skierowany, iloczyn kartezjański, droga (teoria grafów), para uporządkowana oraz graf symetryczny. Przy czym tylko w dwóch ostatnich notacja <x,y> jest niemieszana z (x,y). Wszystkie pozostałe linki, jak również absolutna większość kat. matematyka używa (x,y). Nawet gdyby już ustalono <x,y> (a tego jakoś nigdzie nie widzę, ani tutaj ani na stronie dyskusji medalu) to nie ma to najmniejszego związku z weryfikowalnością, ale z konsensusem i przyjętymi umowami na Wikipedii, nie w literaturze.
• Graf to tylko w uproszczeniu zbiór wierzchołków połączonych krawędziami. To tak jak mówić "grupa to zbiór w którym określono działanie mające pewne własności". W teorii mnogości zawsze abstrahuje się od natury elementów zbioru i od związków między nimi. To oznacza, że {1,2,3} jest zbiorem tak samo "interesującym" jak {1,7,100} czy też {x,y,z}, mimo że w pierwszym zbiorze widać jakąś zależność pomiędzy elementami. "Coś" zawierające 1, 2, 3 w którym połączono 1 i 2 zbiorem już nie jest. Albo "zbiór wierzchołków" albo "zbiór krawędzi" ale nie "zbiór wierzchołków połączonych krawędziami", gdyż w zbiorze możemy określić tylko należenie, a nie łączenie elementów krawędzią. Formalnie: dwa zbiory są równe gdy należą do nich te same elementy. Mamy relację "należenia" lecz nie ma relacji "połączenia" dwóch elementów zbioru. Można mówić o "zbiorze wierzchołków", o "zbiorze krawędzi" ale nie o "zbiorze wierzchołków połączonych krawędziami", gdyż nie ma takiego czegoś w języku matematycznym jak "wierzchołki połączone krawędziami".
• Jeżeli już koniecznie chcemy rozumieć graf jako zbiór, to z definicji G:=<V,E> czy też G:=(V,E) oraz def. Kuratowskiego mamy G = {{V},{V,E}}, czyli: graf jest zbiorem zawierającym (zbiór złożony ze zbioru wierzchołków) oraz (zbiór złożony ze zbioru wierzchołków i zbioru krawędzi).

googl d 13:40, 26 gru 2006 (CET)

Jeżeli nie będzie merytorycznych sprzeciwów zmiany przywrócę za kilka dni. googl d 19:26, 2 sty 2007 (CET)

Z tymi ścisłymi definicjami to jest tak: traktując rzecz czysto formalnie, większość pojęć matematycznych można zdefiniować na różne sposoby, uzyskując struktury formalnie różne, jednak izomorficzne. A matematycy i tak muszą sobie przekodować te formalne definicje na nieformalne ich rozumienie, bo inaczej by nie mogli pracować. Oczywiście muszą często schodzić na poziom formalny, ale to, którą z izomorficznych definicji wybiorą to już sprawa wygody konkretnego zastosowania. Trudno więc powiedzieć, czy ważniejsza jest formalna definicja, czy jej zdroworozsądkowe tłumaczenie. Chyba jednak obydwa są ważne...

Graf jako "zbiór wierzchołków połączonych krawędziami" nie jest formalnie rzecz biorąc w ogóle definicją matematyczną, aczkolwiek nieformalnie chyba mówi więcej niż definicja przez parę (V,E). Najlepiej byłoby chyba umieścić ją jako "intuicyjne rozumienie pojęcia grafu", a obok podać jedną z możliwych formalnych definicji. Ogólnie jednak, skoro już miałbym wybierać z tych dwóch to wersja Googla wydaje mi się sensowniejsza.

Uważam też, że w większości przypadków na wikipedii używana jest dla pary notacja (a,b) a nie <a,b>, więc dobrze byłoby to ujednolicić. Olaf _D 19:45, 2 sty 2007 (CET)

• Ktoś napisał wyżej, że notacja matematyczna jest międzynarodowa. Nie jest to prawdą, notacja nie jest ustalona w żaden sposób, nie ma w tej kwestii międzynarodowych standardów. I prawdę mówiąc - nie są one potrzebne. Wszystko zależy od chwili, przyzwyczajeń, wygody, pogody za oknem, etc.
• Nie wydaje mi się dobrym pomysłem wybór notacji na podstawie ilości artykułów ją używających - liczba ta może okazać się wcale nieadekwatna do ilości osób ją stosujących.
• Z własnego doświadczenia wiem, że notacja (x,y) na oznaczenie pary jest używana w Krakowie (jeżeli na dodatek okaże się że tylko na jednej uczelni to będzie śmiesznie ;) ), natomiast <x,y> jest stosowana we Wrocławiu i Warszawie. Osobiście jestem za notacją <x,y>, ale chyba powinno być jakieś głosowanie (z większą liczbą uczestników, może z portalu:matematyka lub matematyka.org?). Dreamer_ 22:38, 7 sty 2007 (CET)

"Międzynarodowa" = używana na całym świecie, niekoniecznie regulowana przez jakąś umowę. Nie mówię że istnieją jakieś konwencje. Ale takie zapisy jak $e^{x}$ lub $i^{2}=-1$ są rozpoznawalne chyba w większości świata.

Co do notacji, zgadzam się że nie powinno się jej wybierać na podstawie ilości artykułów, nie wiem jak to wygląda na poszczególnych uczelniach. Ale chodziło mi o to, że nie można uzasadniać notacji <a,b> jej "polskością". Jedni piszą tak, drudzy inaczej, zmieniłem na jedną dla konsekwencji. Cytując siebie: "nie mam nic przeciwko konsekwentnemu' stosowaniu notacji <x,y>". Pozdr., googl d 00:03, 27 sie 2007 (CEST)

Wiele krawędzi pomiędzy tymi samymi wierzchołkami

Grafy zdefiniowane tak jak tutaj mogą mieć co najwyżej jedną krawędź pomiędzy tymi samymi wierzchołkami (skierowane - najwyżej dwie w przeciwne strony). Wydaje mi się, że rozważa się też grafy, w których może ich być więcej. Olaf @ 00:09, 9 cze 2007 (CEST)

Czasem się rozważa i jest to ujęte w "warianty definicji". royas 08:03, 9 cze 2007 (CEST)

Faktycznie, nie doczytałem. Dzięki. Olaf @ 10:35, 9 cze 2007 (CEST)

Z Warsztatu PANDA

Nie mam z tym hasłem w zasadzie nic wspólnego, nie jestem autorem (oprócz redakcji przed włożeniem tutaj), po prostu artykuł podoba mi się. Hasło padło już raz w głosowaniu na medal, a potem w DA. Wytknięte braki zostały poprawione, z wyjątkiem dodania informacji o algorytmach grafowych, co uzupełnię przed ewentualnym zgłoszeniem. Formalne kryteria DA hasło chyba spełnia, ale nie ma żadnych przypisów ze szczegółową stroną uźródławiającą każdy akapit. Przypisy tego typu mogliby dodać chyba tylko autorzy, którzy dawno z wikipedii odeszli. Formalnie takie przypisy wymagane na DA nie są, z praktyką bywa różnie. Czy Waszym zdaniem zgłaszać w ogóle coś takiego do DA, a może coś zmienić, coś poprawić? Olaf @ 19:41, 25 sty 2009 (CET)

• Ja tam nie wiem, ale wydaje mi się, że z grubsza wszystko co w tym haśle napisano można znaleźć u cytowanego Willsona. Problematyczne są polskie nazwy (nie tylko tu ale i w całej polskojęzycznej literaturze). Występują różne tłumaczenia a wykładowcy na uczelniach jeszcze czasem pogarszają sytuację rzucając studentom z głowy jakieś radośnie wymyślone tłumaczenie. (Np. "przywieszka") Do informacji o algorytmach można dotrzeć za pomocą szablonu nawigacyjnego z boku. Nawet jeśli nie zakończy się medalem to pobyt w poczekalni na pewno wyjdzie na dobre temu hasłu. Po pierwszym oglądzie nie mogę odnaleźć pojęcia trasowalności i grafów trasowalnych (traceable graphs) ale może jest to pod inną nazwą. Może grymaszę ale fajnie byłoby też znaleźć coś o pakowalności grafów. A już pełnią szczęścia byłoby zobaczyć coś o polskich dokonaniach na polu teorii grafów. Np. wprowadzenie pojęcia jednostajnej trasowalności. -- Miłosz (dyskusja) 20:08, 25 sty 2009 (CET)
  • Dziękuję za opinię. Niestety autorzy sobie poszli, a ja źródeł z teorii grafów nie posiadam. A może sam coś dopisz, bo chyba znasz się na tym temacie? Olaf @ 20:37, 25 sty 2009 (CET)
    • Wstawienie odnośników do konkretnych stron w podanych publikacjach wymaga ich posiadania. Willsona czytałem, ale nie posiadam a pisać, że jest nie sprawdziwszy głupio by było. Co do pozostałych to może coś skrobnę, ale choć miałem to na studiach to nie jest to moja działka i pewne kwestie znam raczej wyrywkowo. Z pewnością nie teraz, zaraz, dziś, ale za jakiś czas może odgrzebię nieco informacji. Pozdrawiam :) -- Miłosz (dyskusja) 21:24, 25 sty 2009 (CET)

Reprezentacje grafu - lista krawędzi

Proponuję dodać jeszcze jedną podstawową reprezentację grafu - listę krawędzi (tylko dla grafów spójnych) - złożoność pamięciowa jedynie O(E) --Falouu (dyskusja) 18:26, 9 cze 2010 (CEST)

Z Wikipedia:Warsztat PANDA

Chciałem zgłosić artykuł do DA, ale nie ma uprawnień, w związku z czym zgłoszenie wycofano. Co do artykułu:

• rozbudowany bardzo, o niebo lepszy niż wersja en, porusza olbrzymią ilość zagadnień i naprawdę ciężko podać coś, czego tutaj nie ma. oczywiście są to opisy raczej "pobieżne", ale taka jest IMHO istota "ogólnego" artykułu (informacje szczegółowe są w artykułach podlinkowych szablonem main)
• dodano praktycznie wszystko czego brak zarzucona artykułowi w przeszłości.. co i tak jest mało istotne, bo nigdzie nie ma zasady mówiącej że
  • dobry artykuł musi być napisany tak, by nie można go było w przyszłości rozbudowywać, bo wszystko już w nim jest
• jest porządna bibliografia. Artykuł w obecnej formie z grubsza wisi już 7-8 lat (od tego czasu zmiany były raczej niewielkie) więc było aż nadto czasu na ew. wytknięcie niezgodności treści artykułu z podanymi źródłami (z powołaniem się na strony w wydaniach książek)

Dałbyś radę pododawać szczegółowe przypisy bibliograficzne do tekstu? Chodzi o to, że np. do rozdziału Warianty definicji wykorzystano pierwszą pozycję w bibliografii, pierwszą i trzecią, czy wszystkie z listy bibliografii? A do napisania np. rozdziału Macierz incydencji użyto której/których książek z bibliografii? Nie wiadomo za bardzo:) Farary (dyskusja) 21:46, 29 kwi 2014 (CEST)

• • posiadam 3 pierwsze (z 5ciu) pozycji w bibliografii, więc to nie problem. Pytanie - gdzie dodać przypisy? Do każdego akapitu? Zdania? Rzucać kostką? najlepiej gdyby ktoś dodał {{fakt}} tam gdzie jego zdaniem informacja wymaga weryfikacji. Inna sprawa, że teraz w necie jest tyle skryptów dostępnych, że można śmiało darować sobie "sztywne" trzymanie się bibliografii zastanej = pytanie tylko jak to jest z "uznawaniem" takich skryptów, czy są jakieś wytyczne typu "doktor hab + z uczelni z <tu wstaw kryterium>"?
  • dodaję po kolei przypisy, wstawiając {{fakt}} tam gdzie nie mogę znaleźć informacji (potem jeszcze kilka razy "przelecę" wszystkie {{fakt}}, bo może coś zostało pominięte). Nie wiem co dalej - {{fakt}} chyba nie może wisieć w nieskończoność i jeżeli nie znajdzie się potwierdzenia, to informacja do usunięcia, tak? Boa Python (dyskusja) 18:26, 30 kwi 2014 (CEST)

Przejrzałam dotychczasowy wkład w hasło i uważam, że obrałeś słuszną strategię. Na koniec pracy z książkami pozostanie uzupełnić o przypisy fragmenty z szablonem {fakt}. Przed zgłoszeniem do DA może lepiej jeszcze zasięgnąć bezpośredniej opinii kogoś aktywnego, kto cokolwiek kuma w matematyce:) Może Wikipedysta:Aegis Maelstrom. Farary (dyskusja) 20:13, 30 kwi 2014 (CEST)

• • Skończyłem z przypisami, myślę że w takiej formie o artykule można powiedzieć, że ma porządne źródła. Dodałem trochę pojęć, kilka obrazków. Część zastanych ujednoliciłem, aczkolwiek wydaje mi się, że dalej idące ujednolicanie grafik mija się z celem - w pewien sposób pokazują, że grafy można różnie rysować, według różnych konwencji. Proszę o opinię czego jeszcze ewentualnie brakuje. Boa Python (dyskusja) 18:32, 14 maj 2014 (CEST)

Wydaje mi się, że należy poprawić sekcję Definicje/Graf. Niejasne, skąd funkcja ϒ? Farary (dyskusja) 19:23, 17 maj 2014 (CEST)

Poprawiłem, faktycznie był tam bałagan - przesunąłem ku górze (do "definicji podstawowej") "prostszą" wersję (występującą np. u Wilsona) operującą tylko pojęciami zbiorów wierzchołków i krawędzi, a do "wariantów definicji" dałem definicję (występująca np. u Wrighta), która wprowadza dodatkowo funkcję ϒ. Boa Python (dyskusja) 09:38, 3 cze 2014 (CEST)

do poprawy

Należy usunąć większość przypisów - źródła powinny być tam, gdzie informacja może budzić wątpliwość. Dodawanie źródeł przy każdym zdaniu (jak w tym artykule) jest absurdem i powinno być jako takie traktowane jak wandalizm, bo naraża wiki na śmieszność. Dodatkowo artykuł jest zbyt rozdmuchany, zamiast skupić się na najważniejszym (grafie jako takim) opisuje okoliczne tematy

Przypisy są bardo ważną częścią Wikipedii pozwalającą na weryfikowanie treści artykułu. Powinny być one po każdym fragmencie tekstu (nie tylko zdaniu, ale nawet pojedynczych wyrazach) który został napisany na podstawie oddzielnych źródeł. Pojedyncze źródło na końcu sekcji ma sens wtedy, gdy cała sekcja została napisana na podstawie danych z jednej pozycji.PuchaczTrado (dyskusja) 11:57, 3 wrz 2014 (CEST)

Zdecydowanie przypisy powinny być obfite. To narzędzie służy do tego żeby wskazać która informacja pochodzi z którego źródła. Powinno być ich tyle żeby co do każdej informacji dało się orzec z którego jest źródła. Marek Mazurkiewicz (dyskusja) 14:27, 3 wrz 2014 (CEST)